% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns
\usepackage{polynom} % long devision
\usepackage{pdfpages} % import pdf pages

\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}


%Add title
\title{Oefeningen TAI: \\
Oefenzitting 7: Decoderen van BCH-codes met het BMF-algoritme}
\date{}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van oefenziting 7 van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants, Miriam De Wolf
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 1 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 1}
Beschouw een BCH-code van lengte $n$ over $GF(q)$ met ontwerpparamters $t$ en $l$. Decodeer het ontvangen woord $v$ m.b.v. het BMF-algoritme (BMF=Berlekamp-Massey en Forney) voor:

(a) $(n,q,t,l) = (5,4,1,2)$ en $v=$ 10 11 11 11 01

(b) $(n,q,t,l) = (15,4,4,1)$ en $v(x) = x^2 + \eta x^5 + \eta^2 x^{13}$ met $\eta^2 + \eta + 1 = 0$

(c) $(n,q,t,l) = (15,11,3,2)$ en $v=$ 3 5 4 3 6 9 10 9 8 10 8 4 6 4 7, waarbij $x^2 + x + 7$ als primitieve veelterm over $GF(11)$ gebruikt wordt en enkele syndromen zijn $S_2 = 10$, $S_3 = 3$, $S_4 = 0$, $S_5 = 8$ en $S_6 = 1$.

Bepaal bij toepassing van het BM-algoritme ook telkens de structuur van de matrix $R^{(t)}$. 

Zie bijlage voor tabellen voor het werken in de respectievelijke velden.






\subsection*{oplossing 1.(a)}
BCH-codes: p.58.\\
Berlekamp-Massey-algoritme: p.75.\\
Forney-algoritme: p.77.\\
Merk op: oefening komt overeen met oefenzitting 6, oef 3.


\vspace{0.7cm}
$n = 5$ (lengte codewoorden)\\
$q = 4$ (code over $GF(4) = GF(2^2)$)\\
$t = 1$ (aantal fouten dat verbeterd moet kunnen worden)\\
$l = 2$ (zie p.58)


\vspace{0.7cm}
$\beta$ = primitieve $5^2$ wortel uit 1 over $GF(4)$.\\
$k$ zo klein mogelijk zodat: $q^k \pmod{5} = 1$ (p.30)\\
$k=1 \Rightarrow 4^1 \pmod{5} = 4  \neq 1$\\
$k=2 \Rightarrow 4^2 \pmod{5} = 1$\\
$\Rightarrow k=2$\\
$\Rightarrow \beta = \alpha^{(4^2 - 1)/5} = \alpha^3$ met $\alpha$ een primitief element van $GF(16)$, nulpunt van $x^2 + \eta x + \eta$ over $GF(4)$.\\
(zie bijlagen, en oefenzitting 6 oef 3)

Bepaal de cyclotomische nevenklassen: (komt overeen met oefenzitting 6 oef 3)\\
$C_{\beta,0} = \{ 0 \} \rightarrow m^{(0)}  = (x - \beta^0) = x + 1$\\
$C_{\beta,1} = \{ 1,4 \} \rightarrow m^{(1)}  = (x - \beta^1)(x - \beta^4) = x^2 + \eta x + 1$\\
$C_{\beta,2} = \{ 2,3 \} \rightarrow m^{(2)}  = (x - \beta^2)(x - \beta^3) = x^2 + \eta^2 x + 1$\\
(zie ook: oefenzitting 5 oef 1.b, oefenzitting 4, oef 3.d, voorbeeld 22, p.25 cursus)

$l = 2$\\
$\Rightarrow g(x) = x^2 + \eta^2 x + 1$


\vspace{0.7cm}
ontvangen woord = $v=$ 10 11 11 11 01\\
$= [10]x^0 + [11]x^1 + [11]x^2 + [11]x^3 + [01]x^4$\\
$= 1 + \eta^2 x + \eta^2 x^2 + \eta^2 x^3 + \eta x^4$

Bepalen syndromen: (p.61)\\
$k=1 \Rightarrow S_1 = v(\beta^{2}) = 1 + \eta^3 \alpha + \eta^4 \alpha^2 + \eta^5 \alpha^3 + \eta^5 \alpha^4 =
1 + \eta \alpha = \alpha^8
$\\
$k=2 \Rightarrow S_2 = v(\beta^{3}) = \alpha^2$




\vspace{0.7cm}
Vervolgens foutlocatorveelterm $\Lambda(x)$ bepalen met behulp van het BM-algoritme p.67.\\
%%%%%% s = 0 %%%%%%
$s=0$

$
\begin{array}{ | c | c | c | c | c | c |}
	\hline
	s	& \Delta	& n		& d		& \Lambda(x)	& \Lambda^{*}(x) \\
	\hline
	0	& /			& 0		& 0		& 1				& 0  \\
	\hline
\end{array}
$\\


%%%%%% s = 1 %%%%%%
$s=1$\\
$\Delta \leftarrow S_1 = \alpha^8 \neq 0$ (alg.4: 3.1. \& 3.2.)\\
$n=0 = d=0$ (alg.4: 3.2.b.)\\
$\Rightarrow$\\
$
\begin{bmatrix}
	\Lambda \\
	\Lambda^{*}
\end{bmatrix}
\leftarrow
\begin{bmatrix}
	x*1 - \alpha^8*0 \\
	1 / \alpha^8
\end{bmatrix}
=
\begin{bmatrix}
	x \\
	\alpha^7
\end{bmatrix}
$ (alg.4: 3.2.b.b.1.)\\
$
\begin{bmatrix}
	n \\
	d
\end{bmatrix}
\leftarrow
\begin{bmatrix}
	0 \\
	0 + 1
\end{bmatrix}
$ (alg4: 3.2.b.b.2.)

$
\begin{array}{| c | c | c | c | c | c |}
	\hline
	s	& \Delta	& n		& d		& \Lambda(x)	& \Lambda^{*}(x) \\
	\hline
	0	& /			& 0		& 0		& 1				& 0 \\
	1	& \alpha^8	& 0		& 1		& x				& \alpha^7 \\
	\hline
\end{array}
$\\



%%%%%% s = 2 %%%%%%
$s=2$\\
$\Delta \leftarrow S_1*0 + S_2*1 = \alpha^2 \neq 0$ (alg.4: 3.1. \& 3.2.)\\
$n=0 < d=1$ (alg.4: 3.2.b.)\\
$\Rightarrow$\\
$\Lambda \leftarrow x - \alpha^2 * x^0 * \alpha^7 = x - \alpha^9 = x + \alpha^9$ (alg.4: 3.2.b.a.1.)\\
$n \leftarrow 0 + 1 = 1$ (alg.4: 3.2.b.a.2.)

$
\begin{array}{| c | c | c | c | c | c |}
	\hline
	s	& \Delta	& n		& d		& \Lambda(x)	& \Lambda^{*}(x) \\
	\hline
	0	& /			& 0		& 0		& 1				& 0 \\
	1	& \alpha^8	& 0		& 1		& x				& \alpha^7 \\
	2	& \alpha^2	& 1		& 1		& x + \alpha^9	& \alpha^7 \\
	\hline
\end{array}
$\\


$n + d = 1 + 1 = 2 = 2*t = 2 \Rightarrow$ stop algoritme met $\Lambda(x) = x + \alpha^9$.



\vspace{0.7cm}
Nu foutwaarden bepalen met het algoritme van Forney (p.77).

Foutenlocaties zijn de nulpunten van: $\Lambda(x) = x + \alpha^9$\\
$\Rightarrow$ aantal fouten $\upsilon = 1$, $X^1 = \alpha^9 = \beta^3$\\
Op de $4^e$ positie zit een fout.

Syndroomveelterm: $S(x) = \alpha^2 + \alpha^8 x$ (p.77)

Fout-evaluatorveelterm: $\Omega(x) = R_{x^2}((\alpha^2 + \alpha^8 x)(x + \alpha^9)) = \alpha^{11}$ (Rest bij deling door $x^2$, p.77)\\
$\Lambda'(x) = 1$

$\Rightarrow Y_1 = - \frac{\Omega(x)}{X_1^4 * \Lambda'(X_1)} = \frac{\alpha^{11}}{\alpha^6} = \alpha^5 = \eta$


\vspace{0.7cm}
Ontvangen woord decoderen:\\
Uit $Y_1 = \eta$ en $X_1 = \beta^3$ volgt:\\ 
$e(x) =$ 0 0 0 $\eta$ 0 \\
$\Rightarrow c(x) = v(x)-e(x) =$ 1 $\eta^2$ $\eta^2$ 1 $\eta$

informatiewoord:\\
$i(x) = c(x)/g(x)=
\begin{array}{c c c}
	1 & 0 & \eta
\end{array}
=
\begin{array}{c c c}
	10 & 00 & 01 
\end{array}
$ (zie oefenzitting 6, oef 3)







\subsection*{oplossing 1.(b)}
$n = 15$ (lengte codewoorden)\\
$q = 4$ (code over $GF(4) = GF(2^2)$)\\
$t = 4$ (aantal fouten dat verbeterd moet kunnen worden)\\
$l = 1$ (zie p.58)


$\beta$ = primitieve $15$-de wortel uit 1 over $GF(4)$.\\
$\Rightarrow \beta = \alpha$ met $\alpha$ een primitief element van $GF(16)$.\\
(zie bijlagen)



\vspace{0.7cm}
ontvangen woord = $v(x) = x^2 + \eta x^5 + \eta^2 x^{13}$

Syndromen:\\
$
\begin{array}{c | c c c c c c c c}
	k	& 1		& 2			& 3			& 4 		& 5 		& 6 		& 7 		& 8 \\
	\hline
	S_k & 0		&\alpha^7	&\alpha^{11}& 0			&\alpha^{10}&\alpha^8	&\alpha^5	&\alpha^{13} 
\end{array}
$

\vspace{0.7cm}
Foutenlocatorveelterm: $\Lambda(x) = \alpha^5 + \alpha^8 x + \alpha^4 x^2 + x^3$\\
Met nulpunten: $X_1 = \beta^2$, $X_2 = \beta^5$, $X_3 = \beta^{13}$\\
Syndroomveelterm: $S(x) = \alpha^{13} + \alpha^5 x + \alpha^8 x^2 + \alpha^{10} x^3 + 0 x^4 + \alpha^{11} x^5 + \alpha^7 x^6$\\
Fout-evaluatorveelterm: $\Omega(x) = \alpha^3 + \alpha^9 x + \alpha^2 x^2$\\
$\Lambda'(x) = \alpha^8 + x^2$

$\Rightarrow$ $Y_1 = 1$, $Y_2 = \alpha^5 = \eta$, $Y_3 = \alpha^{10} = \eta^2$


\vspace{0.7cm}
Ontvangen woord decoderen:\\
$e(x) = x^2 + \eta x^5 + \eta^2 x^{13}$\\
$c(x) = 0$\\
$i(x) = 0$

$R^{(4)} =
\begin{bmatrix}
	0 & \alpha^7 & 0 & 0 \\
	\alpha^7 & \alpha^{11} & 0 & 0 \\
	\alpha^{11} & 0 & \alpha^{12} & 0 \\
	0 & \alpha^{10} & \alpha & 0
\end{bmatrix}
$




\subsection*{oplossing 1.(c)}
$n = 15$ (lengte codewoorden)\\
$q = 11$ (code over $GF(4) = GF(2^2)$)\\
$t = 3$ (aantal fouten dat verbeterd moet kunnen worden)\\
$l = 2$ (zie p.58)


$\beta$ = primitieve $15$-de wortel uit 1 over $GF(11)$.\\
$\Rightarrow \beta = \alpha^8$ met $\alpha$ een primitief element van $GF(121)$.\\
(zie bijlagen)


\vspace{0.7cm}
ontvangen woord = $v =$ 3 5 4 3 6 9 10 9 8 10 8 4 6 4 7

Syndromen:\\
$
\begin{array}{c | c c c c c c }
	k	& 1		& 2			& 3			& 4 		& 5 		& 6 \\
	\hline
	S_k & 1		& 10		& 3			& 0			& 8			& 1 
\end{array}
$


\vspace{0.7cm}
Foutenlocatorveelterm: $\Lambda(x) = 1 + 4 x + x^2$\\
Met nulpunten: $X_1 = \beta^6$, $X_2 = \beta^9$\\
Syndroomveelterm: $S(x) = 1 + 8x + 0x^2 + 3x^3 + 10x^4 + x^5$\\
Fout-evaluatorveelterm: $\Omega(x) = 1 + x$\\
$\Lambda'(x) = 4 + 2 x$

$\Rightarrow$ $Y_1 = 3$,  $Y_2 = 8$


\vspace{0.7cm}
Ontvangen woord decoderen:\\
$e(x) = 3 x^6 + 8 x^9$\\
$c =$ 3 5 4 3 6 9 7 9 8 2 8 4 6 4 7\\
$i = $ 1 2 3 4 5 6 7

$R^{(3)} =
\begin{bmatrix}
	1 & 0 & 0 \\
	10 & 2 & 0 \\
	3 & 3 & 0
\end{bmatrix}
$


 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 2}
(extra) De opeenvolgende waarden $d$ (de graad van $\Lambda(x)$) bij het bepalen van de foutlocatorveelterm met het BM-algoritme zoals beschreven op p.75 van de nota's zijn: 0 0 2 2 2 3 3 3 3 6 6 6 6

(a) Wat zijn de opeenvolgende waarden van $n$?

(b) Welke van de matrices $H^{(k)}$, $k=1,2,\ldots,6$ (def. 33, p.62) zijn regulier en welke zijn singulier?



\subsection*{oplossing 2.a}
$d$ veranderd alleen als $n \geq d$ wordt volgens 3.2.b.b.2. (Algoritme 4 p.75). $n$ veranderd alleen op volgende plaatsen: 3.2.a., 3.2.b.a.2. en 3.2.b.b.2.' hier wordt $n$ ofwel met 1 verhoogd, ofwel krijgt het de vorige waarde van $d$.

Dus:
\begin{tabular}{ c | c c c c c c c c c c c c c }
  $d$ & 0 & 0 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 6 & 6 & 6 & 6 \\
  \hline
  $n$ & 0 & 1 & 0 & 1 & 2 & 2 & 3 & 4 & 5 & 3 & 4 & 5 & 6
\end{tabular}



\subsection*{oplossing 2.b}
Singulier: $det = 0$\\
Regulier: $det \neq 0$

``\ldots, neemt $d$ in het algoritme enkel waarden aan waarvoor $H^{(d)}$ regulier is \ldots'' (p.73 cursus).

$d$ neemt de volgende waarden aan: 0, 2, 3, 6. $\Rightarrow$

$H^{(1)}$: singulier

$H^{(2)}$: regulier

$H^{(3)}$: regulier

$H^{(4)}$: singulier

$H^{(5)}$: singulier

$H^{(6)}$: regulier




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 3}
(extra) Beshouw het algoritme van Forney toegepast op een BCH-code van lengte 11 over GF(4) met ontwerpparamters $t=1$ en $l=3$. Toon aan dat de foutevaluatorveelterm van strikte graad $\upsilon - 1$ is als en slechts als $S_1 \neq 0$.

Voor welke andere waarden van de ontwerpparamter $t$ geldt deze eigenschap ook?\\
(Hint: stelling 22, p.20 kan nuttig gebruikt worden.)


\subsection*{oplossing 3}
$t=1$ en $t=3$



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% include tabellen bijlage 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\includepdf[]{./bijlage/OZ_7_bijlage.pdf}
\end{document}
